package arithmetic.LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 * <p>
 * 回文串 是正着读和反着读都一样的字符串。
 * <p>
 * <p>
 * 示例 1：
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * <p>
 * 示例 2：
 * 输入：s = "a"
 * 输出：[["a"]]
 * <p>
 * 链接：https://leetcode.cn/problems/palindrome-partitioning
 *
 * @author jiangfeng on 2023/4/18
 */
public class PalindromePartition {
    public static void main(String[] args) {
        //System.out.println(new Solution().partition("aab"));
        //System.out.println(new Solution().partition("abbab"));
        System.out.println(new Solution2().partition("abbab"));
    }

    static class Solution2 {
        // 官方写法:
        // 1.先用动态规划思路,计算出所有回文串.  (定义一个二维boolean数组 标识任意长度是否是回文子串).
        // 2.使用回溯算法,定义一个指针为路径,从0开始,当成功识别为回文串时加入结果集并递归到下一层,并在结束时移除结果集,
        //指针到结尾时递归停止
        boolean[][] huiwen;
        int n;
        List<List<String>> result;
        Deque<String> r;
        String ss;

        public List<List<String>> partition(String s) {
            n = s.length();
            huiwen = new boolean[n][n];
            result = new ArrayList();
            r = new ArrayDeque<>();
            ss = s;
            if (n == 1) {
                r.add(s);
                result.add(new ArrayList(r));
                return result;
            }
            for (int i = 0; i < n; i++) {
                Arrays.fill(huiwen[i], true);
            }
            for (int i = 1; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    huiwen[j][i] = s.charAt(i) == s.charAt(j) && huiwen[j + 1][i - 1];
                }
            }
            dfs(0);
            return result;

        }

        public void dfs(int cur) {
            if (cur == n) {
                result.add(new ArrayList(r));
                return;
            }
            for (int i = cur; i < n; i++) {
                if (huiwen[cur][i]) {
                    r.add(ss.substring(cur, i + 1));
                    dfs(i + 1);
                    r.pollLast();
                }
            }
        }
    }

        static class Solution {
        // 一般返回所有解(List<List<String>>)的就需要用到回溯了
        public List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList();
            if (s.length() == 1) {
                List<String> r = new ArrayList();
                r.add(s);
                result.add(r);
                return result;
            }
            // 路径指分割点(在下标所指元素后面),分割点最多为(s.length()-1)个
            // Deque<Integer> path = new ArrayDeque(s.length()-1);
            boolean[] hasPoint = new boolean[s.length() - 1];
            deep(result, 0, hasPoint, s);
            return result;
        }

        public void deep(List<List<String>> result, int deep, boolean[] hasPoint, String s) {
            if (deep == s.length() - 1) {
                // 选择完了
                addResultifCan(result, s, hasPoint);
                return;
            }
            //for (int i = 0; i < s.length() - 1; i++) {
                // 每个断点都有下和不下两个状态.
                // 先是false状态.
                deep(result, deep + 1, hasPoint, s);
                hasPoint[deep] = true;
                deep(result, deep + 1, hasPoint, s);
                // 回退一下状态.
                hasPoint[deep] = false;
            //}
        }

        public void addResultifCan(List<List<String>> result, String s, boolean[] hasPoint) {
            int pre = 0;
            List<String> r = new ArrayList();
            for (int i = 0; i < hasPoint.length; i++) {
                if (hasPoint[i]) {
                    if (!isHui(s, pre, i)) {
                        return;
                    }

                    r.add(s.substring(pre, i + 1));
                    pre = i + 1;
                }
            }
            // 到最后一截
            if (!isHui(s, pre , s.length() - 1)) {
                return;
            }
            r.add(s.substring(pre, s.length()));
            // 符合要求,加入结果集
            result.add(r);
        }

        public boolean isHui(String s, int start, int end) {
            if (start == end) {
                return true;
            }
            while (start <= end) {
                if (s.charAt(start) != s.charAt(end)) {
                    return false;
                }
                start++;
                end--;
            }
            return true;
        }
    }
}
